With rapid advances in semiconductor process technologies and the explosive growth of the consumer electronics market, design of maximum-length sequence generators (MLSGs) to generate binary bit sequences for high-performance applications have drawn attention and reemerged as an important research topic today. These applications range from logic built-in self-test and test compression to cryptography to communications.
Such MLSGs are often realized by maximum-length linear feedback shift registers (LFSRs). These maximum-length LFSRs are typically constructed in a standard or modular form, where one or more XOR gates are interspersed between a flip-flop and the feedback path to generate a desired maximum-length sequence (m-sequence) [1]. If k 2-input XOR gates are required to generate an m-sequence, then the signal on the feedback path would have to propagate through k 2-input XOR gates (as in the standard LFSR) or must be strong enough to drive k+1 fanout nodes (as in the modular LFSR). In either case, the circuit is slowed and may not be applicable for high-performance applications.
To improve the circuit performance (in terms of the number of 2-input XOR gates placed between any two flip-flops and the number of fanout nodes driven by any flip-flop output) and hardware cost (in terms of the total number of 2-input XOR gates required) of these standard and modular LFSRs, many approaches have been proposed. Most noticeable prior art solutions included: 1) hybrid LFSRs that reduce the number of XOR gates from k to (k+1)/2 when the characteristic polynomial generating an m-sequence meets certain requirement [2]; 2) transformed LFSRs that apply a series of transformations to reduce the number of XOR gates and fanout nodes [Rajski patent (2002)]; and 3) ring generators that still use k 2-input XOR gates but can enable each flip-flop output to drive at most 2 fanout nodes and introduce at most one level of one 2-input XOR gate between any two flip-flops [3, 4].
These MLSGs, however, do not offer the combined benefits of using a smaller number of XOR gates and enabling each flip-flop output to drive no more than 2 fanout nodes. In the hybrid LFSR case, while the hardware cost has been reduced for using only (k+1)/2 2-input XOR gates, the rightmost flip-flop would need to pass through one 2-input XOR gate before or after driving (k+1)/2 fanout nodes. Combined with its respective irregularity in design style (due to the long feedback path), this hybrid LFSR may have difficulty to meet frequency requirement for some particular high-performance applications. In the transformed LFSR case, while the number of XOR gates and fanout nodes is reduced, a series of transformations must be performed which could become cumbersome, and the inventors did not teach on how to arrive with using (k+1)/2 2-input XOR gates. In the ring generator case, while the circuit can operate at high speed and result in a simplified layout, its hardware cost is not reduced—it still requires k 2-input XOR gates.
Therefore, there is a need for constructing a new class of high-speed MLSGs referred to as hybrid ring generators that can generate m-sequences or pseudorandom sequences with low hardware cost. When its characteristic polynomial meets certain requirement, the hybrid ring generator will use only (k+1)/2 2-input XOR gates, be able to operate at high speed, and result in a simplified layout. There is also a need for providing a quick visual inspection method and a simple construction method for constructing the hybrid ring generators without going through any transformations.